package com.cqs.leetcode;


import java.util.*;

public class OpenTheLock {


    private int target;
    private Set<Integer> dnums = new HashSet<>();
    private BitSet set = new BitSet();

    //
    public int openLock(String[] deadends, String target) {
        if (deadends != null) {
            for (int i = 0; i < deadends.length; i++) {
                Integer value = Integer.valueOf(deadends[i]);
                if (value == 0) return -1;
                dnums.add(value);
            }
        }
        this.target = Integer.valueOf(target);
        return wfs();
    }

    private int wfs() {
        List<Integer> list = new ArrayList<>();
        list.add(0);
        int step = 0;//死锁
        while (!list.isEmpty()) {
            int size = list.size();
            for (int i = 0; i < size; i++) {
                Integer element = list.remove(0);
                if (element == target) return step;
                for (int j = 0; j < 4; j++) {
                    //向上
                    int bit = bit(element, 3 - j);
                    if (bit != 9) {
                        int up = (int) Math.pow(10, (3 - j)) + element;
                        if (!dnums.contains(up) && !set.get(up)) {
                            set.set(up);//表示进入过列队
                            list.add(up);
                        }
                    }
                    if (bit != 1) {
                        int down = -1;
                        if (bit == 0) {
                            down = element + 9 * (int) Math.pow(10, (3 - j));
                        } else {
                            down = element - (int) Math.pow(10, (3 - j));
                        }
                        if (down <= 0)
                            throw new RuntimeException("j:" + j + "\telement:" + element + " bit:" + bit + "\t" + down);
                        if (!dnums.contains(down) && !set.get(down)) {
                            set.set(down);//表示进入过列队
                            list.add(down);
                        }
                    }
                }
            }
            ++step;
        }
        return -1;
    }

    private int bit(int target, int index) {
        int result = Integer.MAX_VALUE;
        while (index-- > -1) {
            result = target % 10;
            target /= 10;
        }
        return result;
    }

    public static void main(String[] args) {
        String[] deadends = {"8887", "8889", "8878", "8898", "8788", "8988", "7888", "9888"};
//        String[] deadends = {"1111"};
        String target = "8888";
        OpenTheLock lock = new OpenTheLock();
        int result = lock.openLock(deadends, target);
        System.out.println(result);
    }


    private static class Solution {
        List<char[]> roots = new ArrayList<>();
        private int result = Integer.MAX_VALUE;

        private Set<String> deadSet = new HashSet<>();

        private HashSet<String> used = new HashSet<>();


        //迷宫问题
        //DFS
        public int openLock(String[] deadends, String target) {
            char[] chars = new char[4];
            chars[0] = '0';
            chars[1] = '0';
            chars[2] = '0';
            chars[3] = '0';
            for (int i = 0; deadends != null && i < deadends.length; i++) {
                if ("0000".equals(deadends[i])) {
                    return -1;
                }
                deadSet.add(deadends[i]);
            }
            roots.add(Arrays.copyOf(chars, 4));
            wfs(target);
            return result;
        }

        //WFS
        private void wfs(String target) {
            int count = 0;
            while (!roots.isEmpty()) {
                int len = roots.size();
                System.out.println("len:" + len);
                for (int n = 0; n < len; n++) {
                    char[] cs = roots.remove(0);
                    String s = new String(cs);
                    if (equals(s, target)) {
                        if (count < result) result = count;
                        return;
                    } else {
                        for (int i = 0; i < 4; i++) {
                            //up
                            final char c = cs[i];
                            if (c != '9') {
                                cs[i] = upDigit(c);
                                needHandle(cs);
                            }
                            if (c != '1') {
                                cs[i] = downDigit(c);
                                needHandle(cs);
                            }
                            cs[i] = c;
                        }
                    }
                }
                ++count;
            }
            result = -1;
        }

        //下一层要处理的元素
        private void needHandle(char[] cs) {
            String s1 = new String(cs);
            //如何避免的循环处理呢...
            if (!used.contains(s1) && !deadSet.contains(new String(cs))) {
                roots.add(Arrays.copyOf(cs, 4));
                used.add(s1);
            } else {
                System.out.println("dead.." + new String(cs));
            }
        }


        private boolean equals(String cs, String target) {
            return cs.equals(target);
        }

        private char upDigit(char digit) {
            return digit + 1 > '9' ? '0' : (char) (digit + 1);
        }

        private char downDigit(char digit) {
            return digit - 1 < '0' ? '9' : (char) (digit - 1);
        }

        public static void main(String[] args) {
//        String[] deadends = {"8887", "8889", "8878", "8898", "8788", "8988", "7888", "9888"};
            String[] deadends = {"0000"};
            String target = "8888";
            Solution lock = new Solution();
            int i = lock.openLock(deadends, target);
            System.out.println(i);
        }
    }


}
